package com.yangzhe.algorithm.c036;

// 验证完全二叉树
// 测试链接 : https://leetcode.cn/problems/check-completeness-of-a-binary-tree/
public class Code08_CompletenessOfBinaryTree_LeetCode {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }


    private static TreeNode[] queue = new TreeNode[101];

    /**
     * 思路：还是BFS的方式遍历，但是期间根据完全二叉树的特性做判断：
     * 1. 如果子节点中右节点不为空，则左节点一定不为空。否则就出现【洞】
     * 2. 如果当前层是n，则n+1层如果有节点，则n层一定是满的。
     * 2.1 通过遍历n-1层的子节点时，记录第n层是否是满的。第n层满 = 第n-1层所有子节点左节点和右节点都不为空
     * 2.2 如果第n层不满，在遍历第n层时发现n+1层有节点，则不是完全二叉树
     *
     * @param h
     * @return
     */
    public static boolean isCompleteTree(TreeNode h) {
        int l = 0, r = 0;
        queue[r++] = h;

        boolean isPreLevelFull = true;
        while (l < r) {
            TreeNode node = queue[l++];

            // 如果子节点中右节点不为空，则左节点一定不为空。否则就出现【洞】
            if (node.left == null && node.right != null) {
                return false;
            }

            // 如果前一层不是满的，则一定不能有子节点。如果右子节点就有【洞】
            if (!isPreLevelFull && node.left != null) {
                return false;
            }

            if (node.left != null) {
                queue[r++] = node.left;
            } else {
                isPreLevelFull = false;
            }

            if (node.right != null) {
                queue[r++] = node.right;
            } else {
                isPreLevelFull = false;
            }
        }

        return true;
    }

}
